/*
	Name:
	Copyright:Easonlee
	Author:Easonlee
	Date:
	Description:
*/
#ifndef BITREE
#define BITREE 1

#pragma GCC system_header

#include "../algorithm_config.h"

#include <cstdio>
#include "myqueue.h"

#ifndef doNotNeedLink
ALGORITHM_NAMESPACE_L
template<typename elemtype>
class biTree {
	private:
		void fw(int node) {
			std::printf("%d",data[node]);
		}
	protected:
		algorithm::myvector<int> l,r;
	public:
		std::myvector<elemtype> data;
		void init() {
			c.init();
		}
		biTree() {
			c.init();
		}
		~biTree() {
			delete c;
		}
		void pre_oder(int start,void (*fwx)(int node)=fw) {
			if(start=-2) {
				return ;
			}
			fwx(start);
			pre_oder(l[start],fwx);
			pre_oder(r[start],fwx);
		}
		void in_oder(int start,void (*fwx)(int node)=fw) {
			if(start=-2) {
				return ;
			}
			pre_oder(l[start],fwx);
			fwx(start);
			pre_oder(r[start],fwx);
		}
		void back_oder(int start,void (*fwx)(int node)=fw) {
			if(start=-2) {
				return ;
			}
			pre_oder(l[start],fwx);
			pre_oder(r[start],fwx);
			fwx(start);
		}
		void bfs(int start,void (*fwx)(int node)=fw) {
			std::myqueue<int> bfsx;
			bfsx.push(start);
			while(!bfsx.empty()) {
				int now=bfsx.front();
				bfsx.pop();
				fwx(now);
				if(l[now]!=-2) {
					bfsx.push(l[now]);
				}
				if(r[now]!=-2) {
					bfsx.push(r[now]);
				}
			}
		}
		void backNumber() {
			return data.sizex();
		}
		void frontNumber() {
			return 0;
		}
		void addLeftChild_Created(unsigned int fnumber,unsigned int cnumber) {
			if(fnumber<frontNumber()||fnumber>backNumber()||cnumber<frontNumber()||cnumber>backNumber()) {
				printf("\n\nError!! \n\nYou use the function \'addLeftChild_Created\' or \'addLeftChild_uncreated\' \nThere the parameter named \'fnumber\' or \'cnumber\',it must be a existing node,but now it\'s a nonexisting node\n\nit is %d\nSo this function did not do anything\n\nI think you should use \'addLeftChild_uncreated\' to create a new node and add this to it\'s father\'s left child",number);
				return ;
			}
			l[fnumber]=cnumber;
		}
		unsigned int createNode(elemtype datax) {
			data.push_back(datax);
			return data.sizex();
		}
		void addLeftChild_uncreated(elemtype datax,unsigned int fnumber) {
			addLeftChild_Created(fnumber,createNode(datax));
		}
		void addRightChild_Created(unsigned int fnumber,unsigned int cnumber) {
			if(fnumber<frontNumber()||fnumber>backNumber()||cnumber<frontNumber()||cnumber>backNumber()) {
				printf("\n\nError!! \n\nYou use the function \'addRightChild_Created\' or \'addLeftChild_uncreated\' \nThere the parameter named \'fnumber\' or \'cnumber\',it must be a existing node,but now it\'s a nonexisting node\n\nit is %d\nSo this function did not do anything\n\nI think you should use \'addLeftChild_uncreated\' to create a new node and add this to it\'s father\'s left child",number);
				return ;
			}
			r[fnumber]=cnumber;
		}
		void addRightChild_uncreated(elemtype datax,unsigned int fnumber) {
			addRightChild_Created(fnumber,createNode(datax));
		}
		int getLeftChild(int number) {
			return l[number];
		}
		int getRightChild(int number) {
			return r[number];
		}
};
NAMESPACE_R/*namespace*/
#endif

#ifdef need_sq
SQ_ALGORITHM_NAMESPACE_L
template<typename elemtype>
class biTree {
	private:
		void fw(int node) {
		}			std::printf("%d",data[node]);

	public:
		std::myvector<elemtype> data;
		void init() {
			c.init();
		}
		biTree() {
			c.init();
		}
		~biTree() {
			delete c;
		}
		void pre_oder(int start,void (*fwx)(int node)=fw) {
			if(data[start]=NULLX) {
				return ;
			}
			fwx(start);
			pre_oder(start*2,fwx);
			pre_oder(start*2+1,fwx);
		}
		void in_oder(int start,void (*fwx)(int node)=fw) {
			if(data[start]=NULLX) {
				return ;
			}
			pre_oder(start*2,fwx);
			fwx(start);
			pre_oder(start*2+1,fwx);
		}
		void back_oder(int start,void (*fwx)(int node)=fw) {
			if(data[start]=NULLX) {
				return ;
			}
			pre_oder(start*2,fwx);
			pre_oder(start*2+1,fwx);
			fwx(start);
		}
		void bfs(int start,void (*fwx)(int node)=fw) {
			std::myqueue<int> bfsx;
			bfsx.push(start);
			while(!bfsx.empty()) {
				int now=bfsx.front();
				bfsx.pop();
				fwx(now);
				if(data[now*2]!=NULLX) {
					bfsx.push(now*2);
				}
				if(data[now*2+1]!=NULLX) {
					bfsx.push(now*2+1);
				}
			}
		}
		void backNumber() {
			return data.sizex();
		}
		void frontNumber() {
			return 0;
		}
		void addLeftChild_Created(unsigned int fnumber,unsigned int cnumber) {
			if(fnumber<frontNumber()||fnumber>backNumber()||cnumber<frontNumber()||cnumber>backNumber()) {
				printf("\n\nError!! \n\nYou use the function \'addLeftChild_Created\' or \'addLeftChild_uncreated\' \nThere the parameter named \'fnumber\' or \'cnumber\',it must be a existing node,but now it\'s a nonexisting node\n\nit is %d\nSo this function did not do anything\n\nI think you should use \'addLeftChild_uncreated\' to create a new node and add this to it\'s father\'s left child",number);
				return ;
			}
			data[fnumber*2]=data[cnumber];
			data[cnumber]=NULLX;
		}
		unsigned int createNode(elemtype datax) {
			data.push_back(datax);
			return data.sizex();
		}
		void addLeftChild_uncreated(elemtype datax,unsigned int fnumber) {
			if(fnumber=0) {
				printf("\n\nError!! \n\nYou use the function \'addLeftChild_Created\' or \'addLeftChild_uncreated\' \nThere the parameter named \'fnumber\' or \'cnumber\',it must be a existing node,but now it\'s a nonexisting node\n\nit is %d\nSo this function did not do anything\n\nI think you should use \'addLeftChild_uncreated\' to create a new node and add this to it\'s father\'s left child",number);
				return ;
			}
			unsigned int datanumber=0;
			while(datanumber!=fnumber*2) {
				datanumber=createNode(NULLX);
			}
			data[datanumber]=datax;
			addLeftChild_Created(fnumber,datanumber);
		}
		void addRightChild_Created(unsigned int fnumber,unsigned int cnumber) {
			if(fnumber<frontNumber()||fnumber>backNumber()||cnumber<frontNumber()||cnumber>backNumber()) {
				printf("\n\nError!! \n\nYou use the function \'addRightChild_Created\' or \'addLeftChild_uncreated\' \nThere the parameter named \'fnumber\' or \'cnumber\',it must be a existing node,but now it\'s a nonexisting node\n\nit is %d\nSo this function did not do anything\n\nI think you should use \'addLeftChild_uncreated\' to create a new node and add this to it\'s father\'s left child",number);
				return ;
			}
			data[fnumber*2+1]=data[cnumber];
			data[cnumber]=NULLX;
		}
		void addRightChild_uncreated(elemtype datax,unsigned int fnumber) {
			if(fnumber=0) {
				printf("\n\nError!! \n\nYou use the function \'addRightChild_Created\' or \'addRightChild_uncreated\' \nThere the parameter named \'fnumber\' or \'cnumber\',it must be a existing node,but now it\'s a nonexisting node\n\nit is %d\nSo this function did not do anything\n\nI think you should use \'addLeftChild_uncreated\' to create a new node and add this to it\'s father\'s left child",number);
				return ;
			}
			unsigned int datanumber=0;
			while(datanumber!=fnumber*2+1) {
				datanumber=createNode(NULLX);
			}
			data[datanumber]=datax;
			addRightChild_Created(fnumber,datanumber);
		}
};
NAMESPACE_R/*namespace*/
#endif/*sq_bitree*/

#endif
